Many search engine services, such as Google and Overture, provide for searching for information that is accessible via the Internet. These search engine services allow users to search for display pages, such as web pages, that may be of interest to users. After a user submits a search request (i.e., a query) that includes search terms, the search engine service identifies web pages that may be related to those search terms. To quickly identify related web pages, the search engine services may maintain a mapping of keywords to web pages. This mapping may be generated by “crawling” the web (i.e., the World Wide Web) to identify the keywords of each web page. To crawl the web, a search engine service may use a list of root web pages to identify all web pages that are accessible through those root web pages. The keywords of any particular web page can be identified using various well-known information retrieval techniques, such as identifying the words of a headline, the words supplied in the metadata of the web page, the words that are highlighted, and so on. The search engine service identifies web pages that may be related to the search request based on how well the keywords of a web page match the words of the query. The search engine service then displays to the user links to the identified web pages in an order that is based on a ranking that may be determined by their relevance to the query, popularity, importance, and/or some other measure.
Three well-known techniques for page ranking are PageRank, HITS (“Hyperlink-Induced Topic Search”), and DirectHIT. PageRank is based on the principle that web pages will have links to (i.e., “out links”) important web pages. Thus, the importance of a web page is based on the number and importance of other web pages that link to that web page (i.e., “in links”). In a simple form, the links between web pages can be represented by adjacency matrix A, where Aij represents the number of out links from web page i to web page j. The importance score wj for web page j can be represented by the following equation:
      w    j    =            ∑      i        ⁢                  A        ij            ⁢              w        i            
This equation can be solved by iterative calculations based on the following equation:ATw=wwhere w is the vector of importance scores for the web pages and is the principal eigenvector of AT.
The HITS technique is additionally based on the principle that a web page that has many links to other important web pages may itself be important. Thus, HITS divides “importance” of web pages into two related attributes: “hub” and “authority.” “Hub” is measured by the “authority” score of the web pages that a web page links to, and “authority” is measured by the “hub” score of the web pages that link to the web page. In contrast to PageRank, which calculates the importance of web pages independently from the query, HITS calculates importance based on the web pages of the result and web pages that are related to the web pages of the result by following in links and out links. HITS submits a query to a search engine service and uses the web pages of the result as the initial set of web pages. HITS adds to the set those web pages that are the destinations of in links and those web pages that are the sources of out links of the web pages of the result. HITS then calculates the authority and hub score of each web page using an iterative algorithm. The authority and hub scores can be represented by the following equations:
      a    ⁡          (      p      )        =                    ∑                  q          →          p                    ⁢                        h          ⁡                      (            q            )                          ⁢                                  ⁢        and        ⁢                                  ⁢                  h          ⁡                      (            p            )                                =                  ∑                  p          →          q                    ⁢              a        ⁡                  (          q          )                    where a(p) represents the authority score for web page p and h(p) represents the hub score for web page p. HITS uses an adjacency matrix A to represent the links. The adjacency matrix is represented by the following equation:
      b    ij    =      {                            1                                                  ⁢                                          if                ⁢                                                                  ⁢                page                ⁢                                                                  ⁢                i                ⁢                                                                  ⁢                has                ⁢                                                                  ⁢                a                ⁢                                                                  ⁢                link                ⁢                                                                  ⁢                to                ⁢                                                                  ⁢                page                ⁢                                                                  ⁢                j                            ,                                                            0                                                  ⁢            otherwise                              
The vectors a and h correspond to the authority and hub scores, respectively, of all web pages in the set and can be represented by the following equations:a=ATh and h=AaThus, a and h are eigenvectors of matrices ATA and AAT. HITS may also be modified to factor in the popularity of a web page as measured by the number of visits. Based on an analysis of click-through data, bij of the adjacency matrix can be increased whenever a user travels from web page i to web page j.
Although these techniques for ranking web pages based on analysis of links can be very useful, these techniques are susceptible to spamming, both “link spamming” and to some extent “content spamming.” “Spamming” in general refers to a deliberate action taken to unjustifiably increase the rank, relevance, popularity, importance, and so on of a web page or web site. In the case of link spamming, a spammer can manipulate links to unjustifiably increase the importance of a web page. For example, a spammer may increase a web page's hub score by adding out links to the spammer's web page. A common technique for adding out links is to create a copy of an existing link directory to quickly create a very large out link structure. As another example, a spammer may provide a web page of useful information with hidden links to spam web pages. When many web pages point to the useful information, the importance of the spam web pages is indirectly increased. As another example, many web sites, such as blogs and web directories, allow visitors to post links. Spammers can post links to their spam web pages to directly or indirectly increase the importance of the spam web pages. As another example, a group of spammers may set up a link exchange mechanism in which their web sites point to each other to increase the importance of the web pages of the spammers' web sites.
In the case of content spamming, a spammer may create a web page with content that is deliberately added in an attempt to increase the relevance of the web page to certain queries. For example, a web page for a banking service may have hidden data or metadata with the terms “home loans,” “low-cost mortgages,” “no closing costs,” “no points,” “home line of credit,” and so on. The spammer is hoping that the web page will have its relevance increase for queries that relate to home mortgages because of the spam content that has been added. The spam content can be added to any web page of the banking service. For example, the spam “no closing costs” may be added as hidden text to web pages for mortgages that indeed have some closing costs.
Web spam presents problems for various techniques that rely on web data. For example, a search engine service that orders search results in part based on relevance, popularity, or importance of web pages may rank spam web pages unjustifiably high because of the spamming. As another example, a web crawler may spend valuable time crawling the links of spam web sites, which increases the overall cost of web crawling and may reduce its effectiveness. Some techniques have been developed to try to combat spamming. It has, however, been difficult to test the effectiveness of these anti-spamming techniques. First, since the developers of an anti-spamming technique typically provide a search engine service, the developers do not want to intentionally add spam to web pages. In particular, the spam that is introduced for testing purposes may negatively affect the quality of search results provided by their search engine for non-testing purposes. Assuming that the anti-spamming technique is as effective as hoped, then this would not be a problem. However, if the technique is not particularly effective, then the search results for non-testing purposes would be negatively affected by the spam introduced for testing purposes. Second, since it is a time-consuming process to crawl the billions of web pages and generate the various data structures (e.g., content index and web graph and importance scores) used by a search engine, search engine services typically regenerate the data structures only infrequently. As a result, the speed of testing of anti-spamming techniques is constrained by the infrequent updating of the data structures. Third, the developers of anti-spamming techniques typically have to wait until spammers introduce new spam to develop an appropriate anti-spamming technique. Although a developer could proactively introduce spam using a new spamming technique and try to develop an appropriate anti-spamming technique, the introduced spam would negatively affect non-testing search results, and the testing would be slowed by the infrequent updating of the data structures of a search engine.